package com.ycl.javacore.algorithm;

import org.junit.Test;

import java.util.Arrays;

/**
 * User: OF1089 杨成龙
 * Date: 2019/8/17
 * Time: 10:27 PM
 * Desc: 快速排序
 * 选了做左边为基准点，则移动的时候右边先移动
 */
public class AlgoCastQuickSort {

    private void quickSort(int[] nums, int low, int hight) {
        int pivot, temp, i, j;
        if (low > hight) {
            return;
        }
        i = low;
        j = hight;
        pivot = nums[low];

        while (i < j) {
            while (pivot <= nums[j] && i < j) {
                j--;
            }
            while (pivot >= nums[i] && i < j) {
                i++;
            }
            if (i < j) {
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[low] = nums[i];
        nums[i] = pivot;

        quickSort(nums, low, i - 1);
        quickSort(nums, i + 1, hight);
    }

    @Test
    public void test() {
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}
